import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Context class represents a single context characteristic. It stores context ID and valid data ranges, and
 * maps a context value for the specific context to the bucket id numbers.
 * Bucket ID = int representing a range of different possible values for a single context 
 *      characteristic. 
 *    Buckets use Integer.MAX_VALUE and MIN_VALUE to represent infinitely sized ranges.
 * Context ID = integer representing this context characteristic. 
 * 
 * @author Yong Shin
 *
 */
public class Context {

	/** Stores context id */
	private int contextID;
	
	/** Bucket id tree root.  Stores bucket ranges and id's */
	private Node root;
	
	/**
	 * Recursively find the bucket id.
	 * @param node
	 * @param value
	 * @return
	 */
	private int getBucketID(Node node, int value) {
		if (value < node.low) {
			if (node.left != null) 
				return getBucketID(node.left, value);
			else
				throw new RuntimeException("Data outside bucket: context id=" + contextID + ",value=" + value);
		} else if (node.low <= value && value <= node.high) {
			return node.bucketID;
		} else {
			if (node.right != null) 
				return getBucketID(node.right, value);
			else
				throw new RuntimeException("Data outside bucket: context id=" + contextID + ",value=" + value);
		}
	}
	
	/**
	 * Recursively find a context value associated with given bucket id.
	 * @param node
	 * @param bucketID
	 * @return
	 */
	private int getContextForBucketID(Node node, int bucketID) {
		int result = 0;
		if (bucketID == node.bucketID) { 
			// pick a valid value in the range
			if (node.high != Integer.MAX_VALUE)
				result = node.high;
			else 
				result = node.low;
		} else if (bucketID < node.bucketID) {
			if (node.left != null)
				return getContextForBucketID(node.left, bucketID);
			else
				throw new RuntimeException("Invalid bucketID=" + bucketID);
		} else {
			if (node.right != null)
				return getContextForBucketID(node.right, bucketID);
			else
				throw new RuntimeException("Invalid bucketID=" + bucketID);
		}
		return result;
	}
	
	/**
	 * Count the number of nodes in the subtree.
	 * @param node
	 * @return
	 */
	private int getNumberBuckets(Node node) {
		int count = 1;
		if (node.left != null)
			count += getNumberBuckets(node.left);
		if (node.right != null)
			count += getNumberBuckets(node.right);
		return count;
	}
	
	/**
	 * Recursively build String representation.
	 * @param node
	 * @return
	 */
	private String toString(Node node) {
		StringBuilder sb = new StringBuilder();
		if (node.left != null) {
			sb.append(toString(node.left));
			sb.append(' ');
		}
		sb.append(node.toString());
		if (node.right != null) {
			sb.append(' ');
			sb.append(toString(node.right));
		}
		return sb.toString();
	}

	/**
	 * Recursively insert the middle token into the tree.
	 * @param tree
	 * @param tokens
	 * @param start start index (inclusive)
	 * @param end end index (exclusive)
	 */
	private static void insertToken(Context context, ArrayList<String> tokens, int start, int end) {
		
		// end condition
		if (start == end) {
			return;
		}
		
		// insert middle node into the tree
		int mid = (start + end) / 2;
		Node node = context.new Node(tokens.get(mid), mid);
		context.root = insert(context.root, node);
		
		// recursively call insertToken on left half and the right half of the interval
		insertToken(context, tokens, start, mid);
		insertToken(context, tokens, mid+1, end);
	}
	
	/**
	 * Recursively inserts the Node into tree.
	 * @param tree
	 * @param node node to insert
	 * @returns updated tree
	 */
	private static Node insert(Node tree, Node node) {
		if (tree == null) {
			tree = node;
		} else {
			if (node.bucketID < tree.bucketID) {
				tree.left = insert(tree.left, node);
			} else if (node.bucketID > tree.bucketID) {
				tree.right = insert(tree.right, node);
			} else {
				throw new RuntimeException("Duplicate bucket ids:" + node.bucketID);
			}
		}
		return tree;
	}
	
	/** Creates a context for given context id */
	public Context(int contextID) {
		this.contextID = contextID;
	}
	
	/**
	 * Returns context id.
	 * @return
	 */
	public int getContextID() {
		return contextID;
	}
	
	/**
	 * Returns bucket ID corresponding to context value.
	 * @param value
	 * @return
	 */
	public int getBucketID(int value) {
		return getBucketID(root, value);
	}

	/**
	 * Returns any context that belongs in the specified bucket index.
	 * @param bucketID
	 * @return
	 */
	public int getContextForBucketID(int bucketID) {
		return getContextForBucketID(root, bucketID);
	}
	
	/**
	 * Returns the number of buckets for the context.
	 * @return
	 */
	public int getNumberBuckets() {
		return getNumberBuckets(root);
	}

	@Override
	public int hashCode() {
		return contextID;
	}
	
	/**
	 * Two Contexts are equal only if their context id's are the same.  The context parser 
	 * must assure that no two contexts share the same context id.
	 */
	@Override
	public boolean equals(Object obj) {
		boolean result = false;
		if (obj != null) {
			if (obj.getClass() == getClass()) {
				Context other = (Context) obj;
				result = (other.contextID == contextID);
			}
		}
		return result;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(contextID);
		sb.append(": ");
		sb.append(toString(root));
		return sb.toString();
	}
	
	/**
	 * Parses a line of context characteristics file into a context object.
	 * @param data a String containing context data 
	 * @return Context object.
	 */
	public void parse(String line) {
		
		Scanner scan = new Scanner(line);
		
		// read each range values as tokens
		ArrayList<String> tokens = new ArrayList<String>();
		while (scan.hasNext()) {
			tokens.add(scan.next());
		}
		
		// convert tokens into nodes, then recursively insert middle nodes so that
		// the resulting tree will be balanced.
		
		insertToken(this, tokens, 0, tokens.size());
	}

	    // precompile patterns
	    static private Pattern allpat[] = {
		Pattern.compile("(\\d+)\\z"), 	// e.g. "2"
		Pattern.compile("\\((\\-\\d+)\\)\\z"), // e.g. "(-2)"
		Pattern.compile("(\\d+)\\+\\z"), 	// e.g. "2+"
		Pattern.compile("(\\d+)\\-\\z"), 	// e.g. "2-"
		Pattern.compile("\\((\\-\\d+)\\)\\+\\z"), 	// e.g. "(-2)+"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile(""), 	// e.g. "2"
		Pattern.compile("") 	// e.g. "2"
	    };
	
	/**
	 * Node class stores low (inclusive) and high (inclusive) context value
	 * ranges as well as the bucket id corresponding to the values within the range.
	 */
	public class Node {
		
		public int low;
		public int high;
		public int bucketID;
		
		public Node left;
		public Node right;
		
	        public Node (int low, int high, int bucketID) {
			this.low = low;
			this.high = high;
			this.bucketID = bucketID;
			left = right = null;
		}

		
		/**
		 * Creates a Node from token.
		 * @param token
		 * @param bucketID
		 */
		public Node (String token, int bucketID) {
		
			this.bucketID = bucketID;
			
			// parse token using regular expression
			
			Pattern p;
			Matcher m;
			
			if (token.matches("(\\d+)\\z")) {
				p = Pattern.compile("(\\d+)\\z");
				m = p.matcher(token);
				m.matches();
				
				high = low = Integer.parseInt(m.group(1));

                        } else if (token.matches("\\((\\-\\d+)\\)\\z")) {
				// e.g. "(-2)"
				p = Pattern.compile("\\((\\-\\d+)\\)\\z");
				m = p.matcher(token);
				m.matches();
				
				high = low = Integer.parseInt(m.group(1));
                                                
			} else if (token.matches("(\\d+)\\+\\z")) {
				
				// e.g. "2+"
				p = Pattern.compile("(\\d+)\\+\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.parseInt(m.group(1));
				high = Integer.MAX_VALUE;
				
			} else if (token.matches("(\\d+)\\-\\z")) {
				// e.g. "2-"
				p = Pattern.compile("(\\d+)\\-\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.MIN_VALUE;
				high = Integer.parseInt(m.group(1));
				
			} else if (token.matches("\\((\\-\\d+)\\)\\+\\z")) {
				// e.g. "(-2)+"
				p = Pattern.compile("\\((\\-\\d+)\\)\\+\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.parseInt(m.group(1));
				high = Integer.MAX_VALUE;
				
			} else if (token.matches("\\((\\-\\d+)\\)\\-\\z")) {
				// e.g. "(-2)-"
				p = Pattern.compile("\\((\\-\\d+)\\)\\-\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.MIN_VALUE;
				high = Integer.parseInt(m.group(1));
				
			} else if (token.matches("(\\d+)\\-(\\d+)\\z")) {
				// e.g. "1-2"
				p = Pattern.compile("(\\d+)\\-(\\d+)\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.parseInt(m.group(1));
				high = Integer.parseInt(m.group(2));
				
			} else if (token.matches("\\((\\-\\d+)\\)\\-(\\d+)\\z")) {
				// e.g. "(-2)-0"
				p = Pattern.compile("\\((\\-\\d+)\\)\\-(\\d+)\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.parseInt(m.group(1));
				high = Integer.parseInt(m.group(2));
				
			} else if (token.matches("\\((\\-\\d+)\\)\\-\\((\\-\\d+)\\)\\z")) {
				// e.g. "(-2)-(-1)"
				p = Pattern.compile("\\((\\-\\d+)\\)\\-\\((\\-\\d+)\\)\\z");
				m = p.matcher(token);
				m.matches();
				
				low = Integer.parseInt(m.group(1));
				high = Integer.parseInt(m.group(2));
				
			} else {
				throw new RuntimeException("Invalid pattern:" + token);
			}
		}
		
		@Override
		public String toString() {
			StringBuffer sb = new StringBuffer();
			if (low == Integer.MIN_VALUE) {
				sb.append(high);
				sb.append('-');
			} else if (high == Integer.MAX_VALUE) {
				sb.append(low);
				sb.append('+');
			} else if (low == high) {
				sb.append(low);
			} else {
				sb.append(low);
				sb.append('-');
				sb.append(high);
			}
			return sb.toString();
		}
	}
}
